#include<iostream>
#include<stack>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
	int len;
	vector<vector<int> >dp;
    int minCut(string s) {
    	len=s.length();
		dp.assign(len,vector<int>(len,true));
		for(int i=len-1;i>=0;i--)
		for(int j=i+1;j<len;j++)
			dp[i][j]=(s[i]==s[j])&&dp[i+1][j-1];
		vector<int>f(len+1,1000);
		f[0]=-1;
		for(int i = 1; i <= len; i++)
		for(int j = 1; j <=i; j++)
        if(dp[j-1][i-1])
            f[i] = min(f[i], f[j-1] + 1);
        return f[len];
    }
}; 
int main(){
	
	return 0;
}
